Giai đoạn 1511-1526, trong 15 quân đảo trở thành càng biển quan trọng của Đế chế Bồ Đào Nha, trở thành tuyến đường chính đến các đảo Sumatra, Java, Banda, và Maluku.

Năm 1511, người Bồ Đào Nha đánh bại vương quốc Malacca.

Năm 1512, người Bồ Đào Nha thiết lập giao thương với vương quốc Sunda.

Indonesia là một kết hợp của khoảng 250 chủng tộc, phần đông có họ hàng gần gũi với nhau trên quan điểm ngữ học và nhân chủng học: nhóm tộc Mã Lai. Nhiều chủng tộc còn giữ được truyền thuyết là tổ tiên họ di cư đến bằng thuyền từ phương bắc. Trên đảo Java đã đào được nhiều trống đồng cùng kiểu với trống đồng Đông Sơn. Nhiều sách giáo khoa lịch sử Indonesia dạy bài mở đầu với nền văn minh trống đồng.

Theo các tài tiệu có được, từ trên 2000 năm qua, các thương nhân đã đi tàu giữa Trung Hoa và Đông Nam Á, vùng giữa Đông Nam Á và Ấn Độ, tại các đảo ngày nay là Indonesia là nguồn cung cấp gia vị, trầm hương, dược liệu và các sản phẩm nhiệt đới khác. Các thương nhân người Hoa, Ả Rập, Ấn Độ vẫn thường xuyên lui tới các cảng biển ở Indonesia

Những vương quốc cổ xưa nhất của quần đảo này là các nhà nước theo Ấn giáo và Phật giáo, ngày nay tại trung tâm đảo Java tại thành phố Yogyakarta có hai công trình tôn giáo vĩ đại, đền thờ phật Borobudur và đền Ấn giáo Prambanan, cả hai đều được xây bằng đá tại chỗ vào thế kỷ thứ 6 và thế kỷ 8. Các công trình phục chế đã cho thấy vẻ đẹp hùng vĩ của các ngôi đền, quy mô xây dựng và các phù điêu trang trí của nó từ dưới lên trên. Những đền đài này được xây dựng từ thời Phật giáo và Ấn giáo còn thống trị ở Java. Đây cũng là bằng chứng về sự thịnh vượng của các vương quốc trên đảo, ngoài hai ngôi đền trên còn có hàng trăm ngôi đền nhỏ hơn trên khắp Java

Văn minh Ấn Độ truyền đến Indonesia rất sớm, không rõ vào lúc nào. Vào khoảng năm 100 CN, có thái tử Aji Saka dựa theo văn tự Ấn đặt ra văn tự Java. Cũng khoảng đó, xứ Langkasuka được lập ở vùng Kedah, Mã Lai. Đến khoảng năm 500, thì đế quốc lớn đầu tiên được lịch sử ghi nhận của Indonesia là xứ Srivijaya được dựng lên ở phía nam đảo Sumatra. Thủ đô của xứ ấy là thành Palembang, nay là một đô thị đông trên 1.000.000 dân. Trong mấy thế kỷ, Sri-Vijaya hùng cứ những vùng rộng lớn của Java, Sumatra và bán đảo Mã Lai.

Vương quốc SriVijaya có một cường địch là vương quốc Sailendra ở đảo Java. Không rõ Sailendra được lập lúc nào nhưng có lúc họ đô hộ được Thủy Chân Lạp (khoảng 790-802). Các vua Sailendra theo Phật giáo, tôn giáo được truyền đến vùng này vào khoảng năm 450. Từ khoảng 770 đến 825, 3 vua Sailendra nối nhau xây chùa Borobudur, nay vẫn là ngôi chùa Phật lớn nhất thế giới.

Không bao lâu sau, nhà Sanjaya rất sùng đạo Ấn giáo thắng Sailendra. Ấn giáo dần dần thay thế Phật giáo ở Java. Vào khoảng năm 985, vua Dharmavamsa ở đông bộ Java, Bali và tây bộ đảo Kalimantan ra lệnh dịch trường ca Mahabharata của Ấn giáo, dài hơn 200.000 câu, sang tiếng Java. Đời vua Joyoboyo, hậu duệ của ông trị vì từ 1135 đến 1157, được coi là thời vàng son của văn học tiếng Java.

Năm 1222, vương quốc Singhasari được thành lập ở đông bộ Java, nhanh chóng trở thành thế lực lớn nhất nhì của quần đảo. Singhasari đánh đuổi được quân xâm lược Mông Cổ năm 1293, rồi đổi quốc hiệu thành Majapahit. Năm 1319, một viên tướng thủ lĩnh ngự lâm quân là Gajah Mada dần dần nắm hết mọi quyền bính trong triều. Từ 1319 đến 1364, Gajah Mada bành trướng Majapahit thành rộng lớn như Indonesia ngày nay, có thêm miền nam của Philippines.